# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        #
    #     if not root:
    #         return root
    #     a = []
    #     m =self.inorder(root,a)
    #     h = [i.val for i in m]
    #     s= [h[-1]] * len(h)
    #     for j in range(len(h)-2,-1, -1):
    #         s[j] = s[j+1]+h[j]
    #     for i,j in enumerate(m):
    #         j.val = s[i]
    #     return root
    #     # for i in range(len(m)):
    #     #     for j in range(i+1,len(m)):
    #     #         m[i].val += m[j].val
    #     #         j+=1
    #     #     i+=1
    #     return root
    # def inorder(self,node,a):
    #     if not node:
    #         return []
    #     self.inorder(node.left,a)
    #     a.append(node)
    #     self.inorder(node.right,a)
    #     return a\
        deque = []
        a= []
        if not root:
            return []
        node = root
        while node or deque:
            while node:
                deque.append(node)
                node =node.left
            node = deque.pop()
            a.append(node)
            node = node.right
        tmp = 0
        for j in range(len(a)-1,-1,-1):
            a[j].val += tmp
            tmp = a[j].val
        return root





m1 = TreeNode(5)
m1.left = TreeNode(2)
m1.right = TreeNode(13)
# m1.right.left = TreeNode(2)
# m1.right.right = TreeNode(3)
s = Solution()

t = s.convertBST(m1)
print(t)
